package com.lw.leetcode.dp.b;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * 22. 括号生成
 * 剑指 Offer II 085. 生成匹配的括号
 * 面试题 08.09. 括号
 *
 * @author liw
 * @version 1.0
 * @date 2021/8/19 14:03
 */
public class GenerateParenthesis {
    public List<String> generateParenthesis(int n) {

        List<String> a = new ArrayList<>();
        if (n < 1) {
            return a;
        }
        a.add("()");
        if (n == 1) {
            return a;
        }
        List<String> b = new ArrayList<>();
        for (int i = 2; i <= n; i++) {
            for (String s : a) {
                b.add("()" + s);
                int[] aa = find(s);
                for (int d : aa) {
                    if (d == 0) {
                        break;
                    }
                    b.add("(" + s.substring(0, d) + ")" + s.substring(d));
                }
            }
            a = b;
            b = new ArrayList<>();
        }
        return a;
    }

    private int[] find(String s) {
        char[] chars = s.toCharArray();
        int length = s.length();
        int[] arr = new int[length >> 1];
        int a = 0;
        int b = 0;
        int n = 0;
        for (int i = 0; i < length; i++) {
            if (chars[i] == '(') {
                a++;
            } else {
                b++;
            }
            if (a == b) {
                arr[n++] = i + 1;
            }
        }
        return arr;
    }
}
